{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# [Kadane's Algorithm](http://www.algorithmist.com/index.php/Kadane's_Algorithm)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Kadane's Algorithm** is an _O_(_n_) algorithm for finding the maximum contiguous [subsequence](/index.php/Subsequence \"Subsequence\") in a one-dimensional [sequence](/index.php/Sequence \"Sequence\").\n",
    "\n",
    "\n",
    "**Kadane算法**是用于寻找一维[数组](/index.php/Sequence \"Sequence\")最大连续[子集](/index.php/Subsequence \"Subsequence\")，复杂度_O_(_n_)。\n",
    "\n",
    "<!-- TEASER_END -->\n",
    "\n",
    "```\n",
    "begin\n",
    "    (maxSum, maxStartIndex, maxEndIndex) := (-INFINITY, 0, 0)\n",
    "    currentMaxSum := 0\n",
    "    currentStartIndex := 1\n",
    "    for currentEndIndex := 1 to n do\n",
    "        currentMaxSum := currentMaxSum + array[currentEndIndex]\n",
    "        if currentMaxSum > maxSum then\n",
    "            (maxSum, maxStartIndex, maxEndIndex) := (currentMaxSum, currentStartIndex, currentEndIndex)\n",
    "        endif\n",
    "\n",
    "        if currentMaxSum < 0 then\n",
    "            currentMaxSum := 0\n",
    "            currentStartIndex := currentEndIndex + 1\n",
    "        endif\n",
    "    endfor\n",
    "\n",
    "    return (maxSum, maxStartIndex, maxEndIndex)\n",
    "end\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def max_subarray(A):\n",
    "    maxSum, maxStartIndex, maxEndIndex = A[0], 0, 0\n",
    "    currentMaxSum = 0\n",
    "    currentStartIndex = 0\n",
    "    for currentEndIndex, item in enumerate(A):\n",
    "        currentMaxSum = currentMaxSum + A[currentEndIndex]\n",
    "        if currentMaxSum > maxSum:\n",
    "            maxSum, maxStartIndex, maxEndIndex = currentMaxSum, currentStartIndex, currentEndIndex\n",
    "        if currentMaxSum < 0:\n",
    "            currentMaxSum = 0\n",
    "            currentStartIndex = currentEndIndex + 1\n",
    "    return (maxSum, maxStartIndex, maxEndIndex, A[maxStartIndex:maxEndIndex+1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "最大连续子集：\n",
      "和为6，起止下标3，6。\n",
      "子集为[4, -1, 2, 1]\n"
     ]
    }
   ],
   "source": [
    "x = [-2, 1, -3, 4, -1, 2, 1, -5, 4]\n",
    "print u'最大连续子集：\\n和为{}，起止下标{}，{}。\\n子集为{}'.format(*max_subarray(x))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<iframe width=\"800\" height=\"500\" frameborder=\"0\" src=\"http://pythontutor.com/iframe-embed.html#code=def+max_subarray(A)%3A%0D%0A++++maxSum,+maxStartIndex,+maxEndIndex+%3D+A%5B0%5D,+0,+0%0D%0A++++currentMaxSum+%3D+0%0D%0A++++currentStartIndex+%3D+0%0D%0A++++for+currentEndIndex,+item+in+enumerate(A)%3A%0D%0A++++++++currentMaxSum+%3D+currentMaxSum+%2B+A%5BcurrentEndIndex%5D%0D%0A++++++++if+currentMaxSum+%3E+maxSum%3A%0D%0A++++++++++++maxSum,+maxStartIndex,+maxEndIndex+%3D+currentMaxSum,+currentStartIndex,+currentEndIndex%0D%0A++++++++if+currentMaxSum+%3C+0%3A%0D%0A++++++++++++currentMaxSum+%3D+0%0D%0A++++++++++++currentStartIndex+%3D+currentEndIndex+%2B+1%0D%0A++++return+(maxSum,+maxStartIndex,+maxEndIndex,+A%5BmaxStartIndex%3AmaxEndIndex%2B1%5D)%0D%0A++++%0D%0Ax+%3D+%5B-2,+1,+-3,+4,+-1,+2,+1,+-5,+4%5D%0D%0A%0D%0Amax_subarray(x)&origin=opt-frontend.js&cumulative=false&heapPrimitives=false&drawParentPointers=false&textReferences=false&showOnlyOutputs=false&py=2&rawInputLstJSON=%5B%5D&curInstr=52&codeDivWidth=350&codeDivHeight=400\"> </iframe>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML at 0x7faf300476d0>"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from IPython.display import HTML\n",
    "HTML('<iframe width=\"800\" height=\"500\" frameborder=\"0\" src=\"http://pythontutor.com/iframe-embed.html#code=def+max_subarray(A)%3A%0D%0A++++maxSum,+maxStartIndex,+maxEndIndex+%3D+A%5B0%5D,+0,+0%0D%0A++++currentMaxSum+%3D+0%0D%0A++++currentStartIndex+%3D+0%0D%0A++++for+currentEndIndex,+item+in+enumerate(A)%3A%0D%0A++++++++currentMaxSum+%3D+currentMaxSum+%2B+A%5BcurrentEndIndex%5D%0D%0A++++++++if+currentMaxSum+%3E+maxSum%3A%0D%0A++++++++++++maxSum,+maxStartIndex,+maxEndIndex+%3D+currentMaxSum,+currentStartIndex,+currentEndIndex%0D%0A++++++++if+currentMaxSum+%3C+0%3A%0D%0A++++++++++++currentMaxSum+%3D+0%0D%0A++++++++++++currentStartIndex+%3D+currentEndIndex+%2B+1%0D%0A++++return+(maxSum,+maxStartIndex,+maxEndIndex,+A%5BmaxStartIndex%3AmaxEndIndex%2B1%5D)%0D%0A++++%0D%0Ax+%3D+%5B-2,+1,+-3,+4,+-1,+2,+1,+-5,+4%5D%0D%0A%0D%0Amax_subarray(x)&origin=opt-frontend.js&cumulative=false&heapPrimitives=false&drawParentPointers=false&textReferences=false&showOnlyOutputs=false&py=2&rawInputLstJSON=%5B%5D&curInstr=52&codeDivWidth=350&codeDivHeight=400\"> </iframe>')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}
